# -*- coding=utf-8 -*-
# 给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合
# candidates 中的每个数字在每个组合中只能使用一次

# 说明：
# 所有数字（包括目标数）都是正整数
# 解集不能包含重复的组合

# 示例 1:
# 输入: candidates = [10,1,2,7,6,1,5], target = 8,
# 所求解集为:
# [
#   [1, 7],
#   [1, 2, 5],
#   [2, 6],
#   [1, 1, 6]
# ]

# 示例 2:
# 输入: candidates = [2,5,2,1,2], target = 5,
# 所求解集为:
# [
#   [1,2,2],
#   [5]
# ]

# class Solution(object):
#     def combinationSum2(self, candidates, target):
#         """
#         :type candidates: List[int]
#         :type target: int
#         :rtype: List[List[int]]
#         """
#         candidates.sort();

#         rtn = [];
#         def rpc(remain, path, index):
#             if remain == 0:
#                 if path not in rtn:
#                     rtn.append(path);
#                 return;

#             if index > len(candidates) - 1:
#                 return;

#             for i in xrange(index, len(candidates)):
#                 if remain < candidates[i]:
#                     break;
#                 rpc(remain - candidates[i], path + [candidates[i]], i + 1);

#         rpc(target, [], 0);

#         return rtn;






# 查看最快的解决方案
class Solution(object):
    def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        candidates.sort();

        rtn = [];
        def rpc(remain, path, index):
            if remain == 0:
                rtn.append(path);
                return;

            if index > len(candidates) - 1:
                return;

            for i in xrange(index, len(candidates)):
                if remain < candidates[i]:
                    break;

                # 每次填充时都不重复填充
                # eg: 输入[1, 1, 1, 2, 3, 5], 8
                # 按照上面的算法
                # 第一层循环时的path分别是
                # [1]   T
                # [1]   T
                # [1]   T
                # [2]
                # [3]
                # [5]
                # 第二层循环时, 只针对前4个
                # [1, 1]    T
                # [1, 1]    T
                # [1, 2]
                # #
                # [1, 1]    T
                # [1, 2]
                # #
                # [1, 2]
                # ......................
                # 由上面我们可以看到当我们在第一层循环时，插入的candidates[0]实际上已经包含了candidates[1],candidates[2]这两种情况
                # 由此我们可以总结出在同一层循环时，我们没有必要插入相同的元素，避免重复计算，也避免了最终统计结果时的出重操作
                if i > index and candidates[i] == candidates[i - 1]:
                    continue;

                rpc(remain - candidates[i], path + [candidates[i]], i + 1);

        rpc(target, [], 0);

        return rtn;

t = Solution();
print t.combinationSum2([10,1,2,7,6,1,5], 8);